package leetcode.code0084;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution84_1 implements IDebug {
	public static void main(String[] args) {
		Solution84_1 so = new Solution84_1();
		so.debug1();
		so.debug2();
		so.debug3();
	}

	public int largestRectangleArea(int[] heights) {
		int len = heights.length;
		int ans = 0;
		int[] s = new int[len + 1];
		s[0] = -1;
		int p = 0;
		for (int i = 0; i < len; i++) {
			if (p > 0 && heights[s[p]] >= heights[i]) {
				int right = s[p];
				do {
					int index = s[p--];
					ans = Math.max(ans, (right - s[p]) * heights[index]);
				} while (p > 0 && heights[s[p]] >= heights[i]);
			}
			s[++p] = i;
		}
		int right = s[p];
		while (p > 0) {
			int index = s[p--];
			ans = Math.max(ans, (right - s[p]) * heights[index]);
		}
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[2,1,5,6,2,3]";
		int e = 10;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,4]";
		int e = 4;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[4,2,0,3,2,5]";
		int e = 6;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

}
